//平衡二叉树是指每一个节点的左子树和右子树的高度差的绝对值不超过1
//高度是指该节点到叶子节点的距离，
//而对于最大高度来说，也可以理解为该节点到叶子节点的最大深度
//使用递归法或迭代法

/*
深度：从根节点到该节点的最长路径边数（或节点数）

高度：从该节点到叶子节点的最长路径边数（或节点数）

*/
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
};


//递归法
//在递归法中，有一处和求树的最大深度很像，因为要求该节点对于其子树的最大高度，只需求以该节点为根节点的最大深度
#include <algorithm>
#include <cmath>
using std::max;
using std::abs;
int getDepth(TreeNode* node)
{
    if(!node) return 0;
    int ldepth=getDepth(node->left);
    int rdepth=getDepth(node->right);

    //求出左右子树高度后判断左右子树是否平衡二叉树，若不是，则-1标记
    //-1标记表示左右子树不是平衡二叉树，那整棵树不是平衡二叉树
    if(ldepth==-1||rdepth==-1) return -1;
    //
    return abs(ldepth-rdepth)>1? -1:1+max(ldepth,rdepth);   //当子树平衡，就求该子树的高度（最大深度）
                                    //这一段就是通过求最大深度来求最大高度
}
bool isBalanced_recursion(TreeNode* root)
{
    return getDepth(root)==-1? false:true;
}



//迭代法
//先做出一个求最大高度的函数，然后迭代进行比较
#include <queue>
using std::queue;
int getDepth(TreeNode* node) //参见求最大深度方法，用递归、队列、栈（难理解）都可以
{
if(!node) return 0;
queue<TreeNode*> que;
que.push(node);
int depth=0;
while(!que.empty())
{
    int size=que.size();
    depth++;
    for(int i=0;i<size;i++)
    {
        TreeNode* node=que.front();
        que.pop();
        if(node->left) que.push(node->left);
        if(node->right) que.push(node->right);

    }
}
return depth;
}

#include <stack>
using std::stack;
int isBalanced(TreeNode* root)
{
    if(!root) return true;
    stack<TreeNode*> st;
    st.push(root);
    while(!st.empty())
    {
        TreeNode* node=st.top();
        st.pop();
        if(abs(getDepth(node->left)-getDepth(node->right))>1) return false;
        if(node->left) st.push(node->left);
        if(node->right) st.push(node->right);
    }
    return true;
}



//跟递归不同的是，递归是先验证子树是否平衡二叉树，再验证整棵树是不是平衡二叉树
//而迭代是先验证整棵树的最大深度满不满足平衡二叉树，再下到每个节点验证